/*
 * @lc app=leetcode id=705 lang=cpp
 *
 * [705] Design HashSet
 */
struct Node {
    Node(int key):key(key), next(0) {}
    int key;
    Node *next;
};


class MyHashSet {
public:
    /** Initialize your data structure here. */
    MyHashSet() {
        tsize_ = DefaultSize;
        table_ = new Node*[tsize_]();
    }
    
    void add(int key) {
        int idx = getIdx(key);
        assert(idx >= 0 && idx < tsize_);

        Node* node = table_[idx];
        if (node) {

            if (node->key == key) {
                return ;
            }

            while (node->next && node->next->key != key) {
                node = node->next;
            }

            if (!node->next) {
                node->next = new Node(key);
            }
        } else {
            table_[idx] = new Node(key);
        }
    }

    void remove(int key) {
        int idx = getIdx(key);
        assert(idx >= 0 && idx < tsize_);

        Node* node = table_[idx];
        if (node) {
            if (node->key == key) {
                table_[idx] = node->next;
                delete node;
            } else {
                while(node->next && node->next->key != key) {
                    node = node->next;
                }

                if (node->next && node->next->key == key) {
                    Node *toBeDelete = node->next;
                    node->next = node->next->next;
                    delete toBeDelete;
                }
            }
        }
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        int idx = getIdx(key);
        assert(idx >= 0 && idx < tsize_);

        Node* node = table_[idx];
        if (node) {
            while (node && node->key != key) {
                node = node->next;
            }
            if (node) {
                return true;
            }
        } 
        return false;
    }
private:


    int hash_(int key) {
        unsigned int hash = 5381;
        hash = (hash << 5) + hash + key;
        return hash;
    }

    int getIdx(int key) {
        int idx = hash_(key) % tsize_;
        return idx;
    }

    Node** table_;
    size_t tsize_;
    const static size_t DefaultSize = 256;

};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

